import java.util.ArrayList;

/**
 * Created by L.jp
 * Description:输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
 * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
 * 2.叶子节点是指没有子节点的节点
 * 3.路径只能从父节点到子节点，不能从子节点到父节点
 * 4.总节点数目为n
 * User: 86189
 * Date: 2021-12-26
 * Time: 12:40
 */
/*输入：
        {10,5,12,4,7},22

        返回值：
        [[10,5,7],[10,12]]   //结果集合里面，放的都是单独的一个待选集合
        */
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class BinaryTree {
    public void FindPathHelper(TreeNode root,int expectNumber,ArrayList<Integer> tmp,ArrayList<ArrayList<Integer>> ret){
        //到了叶子结点的子树，其值为null,才可以返回路径
        if(root==null){
            return;
        }
        //将节点的值加入到待选集
        tmp.add(root.val);
        //加入之后，采用目标值不断减的做法，更新目标值
        expectNumber-= root.val;
        //直到遍历到叶子结点，并且目标值减为0时，说明这个路径总和与目标值相等，符合要求，将待选集加入到结果集
        if(root.left==null && root.right==null && expectNumber==0){//剪枝思想，去掉不符合结果的节点
            ret.add(new ArrayList<>(tmp));//不是让tmp的集合持续加入到结果集中，每递归一次都要创建一个新的待选集，然后将tmp的集合放进去
        }
        //因为每次都是先加入节点的值，然后再更新目标值，然后再判断目标值是否减为了0，为0就加入到结果集，然后再到左右子树遍历，这是一个重复的操作，所以递归
       //递归左子树
        FindPathHelper(root.left,expectNumber,tmp,ret);
        //递归右子树
        FindPathHelper(root.right,expectNumber,tmp,ret);
        //遍历完后，说明符合情况，然后再回退到上一个根节点，继续判断
        //这里通过在待选集里删除最后一个元素的方式来回退
        //回溯
        tmp.remove(tmp.size()-1);
    }
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int expectNumber) {
        if(root==null){
            return  new ArrayList<>();
        }
        //待选结果
        ArrayList<Integer> tmp=new ArrayList<>();
        //最终结果集
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        FindPathHelper(root,expectNumber,tmp,ret);
        return  ret;
    }
}
